package ysf.com.simplediffculty;

import java.io.Serializable;

/**
 * @author ysf
 * @date 2021/6/25 21:55
 *
 */
public class FourteenthDemos implements Serializable {

    public static void main(String[] args) {
        String[] str = new String[]{"flower","flow","flight"};
        String s = longestCommonPrefix(str);
        System.out.println(s);
    }


    public static String longestCommonPrefix(String[] strs){
        if(strs == null || strs.length == 0){
            return "";
        }
        return longestCommonPrefix(strs, 0 , strs.length - 1);
    }

    //递归不断分成两部分
    private static String longestCommonPrefix(String[] strs, int l, int r) {
        if (l == r) {
            return strs[l];
        } else {
            int mid = (l + r)/2;
            String lcpLeft = longestCommonPrefix(strs, l , mid);
            String lcpRight = longestCommonPrefix(strs, mid + 1,r);
            String s = commonPrefix(lcpLeft, lcpRight);
            System.out.println(s);
            return commonPrefix(lcpLeft, lcpRight);
        }
    }

    //求两个结果的最⻓公共前缀
    static String commonPrefix(String left,String right) {
        int min = Math.min(left.length(), right.length());
        for (int i = 0; i < min; i++) {
            if ( left.charAt(i) != right.charAt(i) ){
                return left.substring(0, i);
            }
        }
        return left.substring(0, min);
    }



}
